package com.hyb.algorithm.data.struct.backtrack;

import java.util.*;

/**
 * 47. 全排列 II
 * https://leetcode.cn/problems/permutations-ii/description/
 *
 * 参考 题解 https://leetcode.cn/problems/permutations-ii/solutions/417937/quan-pai-lie-ii-by-leetcode-solution/
 *
 * @author: ybhu
 * @create: 2023/12/28 19:32
 */
public class PermuteUnique2 {



    private   List<List<Integer>> res;

    public List<List<Integer>> permuteUnique(int[] nums) {

        res=new ArrayList<List<Integer>>();
        boolean[] used=new boolean[nums.length];

        //先做一次排序
        Arrays.sort(nums);
        backTack(nums,0,new ArrayList<Integer>(),used);
        return res;
    }

    public void backTack(int[] nums,int count,List<Integer> list ,boolean[] used){

        //递归终止条件
        if(count==nums.length){
            //深度拷贝
            res.add(new ArrayList(list));

            return;
        }

        for(int i=0;i<nums.length;i++){

            //要解决重复问题，我们只要设定一个规则，保证在填第 idx\textit{idx}idx 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }

            if(!used[i]){
                list.add(nums[i]);
                used[i]=true;
                //回溯
                backTack(nums,count+1,list,used);
                used[i]=false;
                list.remove(list.size()-1);
            }
        }
    }

}
